package main.java.LeetCode.ClassicalAlgorithm.Graph.Impl;

import main.java.LeetCode.ClassicalAlgorithm.Graph.Graph;

import java.util.*;

public class LinkedGraph implements Graph {

    private final HashMap<Integer, HashMap<Integer,Integer>> graph;

    private final HashSet<Integer> nodes;



    public LinkedGraph(){
        graph = new HashMap<>();
        nodes = new HashSet<>();
    }

    @Override
    public void addEdge(int start, int end, int distance) {
        HashMap<Integer, Integer> map = graph.computeIfAbsent(start, k -> new HashMap<>());
        map.put(end, distance);
        nodes.add(start);
        nodes.add(end);
    }

    @Override
    public int getMinDistance(int start, int end) {
        if(!nodes.contains(start)||!nodes.contains(end))
            return -1;
        if(start==end)
            return 0;

        HashMap<Integer, Integer> distance = new HashMap<>();
        LinkedList<Integer> queue = new LinkedList<>();
        HashSet<Integer> set = new HashSet<>();


        queue.addLast(start);
        set.add(start);
        distance.put(start,0);

        while (!queue.isEmpty()){
            int s = queue.removeFirst();
            set.remove(s);

            HashMap<Integer, Integer> ends;
            if((ends = graph.get(s))==null)
                continue;

            Set<Integer> e = ends.keySet();

            for(int node:e){
                if(!distance.containsKey(node)||distance.get(node)>distance.get(s)+ends.get(node)) {
                    distance.put(node, distance.get(s) + ends.get(node));

                    if(!set.contains(node)) {
                        set.add(node);
                        queue.addLast(node);
                    }
                }
            }
        }
        return distance.getOrDefault(end, -1);
    }

}
